package minimumDifference;
import java.util.Arrays;
import java.util.Map;

public class Solution {
    public int minimumDifference(int[] nums, int k) {
        // 思路 极差最小
        // 每个学生可以选 也可以不选
        // 如果选 dp[i][j] = nums[i] - nums[i-j+1] 如果不选 dp[i-1][j]
        // 必须要选j个 if(i<=j-1) dp[i][j] = dp[i] - dp[0]

        // dp[1][1] = 0
//        Arrays.sort(nums);
//        int m = nums.length;
//        int[][] dp = new int[m][k+1];
//        for (int j = 2; j <= k; j++) {
//            for (int i = 1; i < m; i++) {
//                if(i<=j-1){
//                    dp[i][j] = nums[i] - nums[0];
//                }else {
//                    dp[i][j] = Math.min(nums[i] - nums[i-j+1],dp[i-1][j]);
//                }
//            }
//        }
//        return dp[m-1][k];

        // 排序 + 滑动窗口
        Arrays.sort(nums);
        int l = 0;
        int r = k-1;
        int ans = nums[r] - nums[l];
        while (r<nums.length){
            ans = Math.min(ans,nums[r] - nums[l]);
            l++;
            r++;
        }
        return ans;
    }
    private void quickSort(int[] nums){
        quick_sort(nums,0,nums.length-1);
    }
    private void quick_sort(int[] nums,int l,int r){
        if(l<r){
            int pivot = partition(nums,l,r);
            quick_sort(nums,l,pivot-1);
            quick_sort(nums,pivot+1,r);
        }
    }
    private int partition(int[] nums,int l,int r){
        int pivot = nums[l];
        int left = l;
        int right = r;
        while (left<right){
            while (left<right&&nums[right]>=pivot){
                right--;
            }
            nums[left] = nums[right];
            while (left<right&&nums[left]<=pivot){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[right] = pivot;
        return right;
    }
}
